package Tree.BST;

import Utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉搜索树的最小绝对差
 * 给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
 *
 *  
 *
 * 示例：
 *
 * 输入：
 *
 *    1
 *     \
 *      3
 *     /
 *    2
 *
 * 输出：
 * 1
 *
 * 解释：
 * 最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class getMinimumDifference {
    private List<Integer> list = new ArrayList<>();

    TreeNode preNode = null;

    int minDiff = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
//        priTraversal(root);
//        int min = Integer.MAX_VALUE;
//        for (int i = 1; i < list.size(); i++) {
//            int minus = list.get(i) - list.get(i - 1);
//            if (minus < min) {
//                min = minus;
//            }
//        }
//        return min;
        inOrder(root);
        return minDiff;
    }

    private void priTraversal(TreeNode root) {
        if (root == null) return;
        priTraversal(root.left);
        list.add(root.val);
        priTraversal(root.right);
    }

    private void inOrder(TreeNode node) {
        if (node == null) return;
        inOrder(node.left);
        if (preNode != null) minDiff = Math.min(minDiff, node.val - preNode.val);
        preNode = node;
        priTraversal(node.right);
    }
}
